#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int getPriority(char op)
{
    int p;
    switch (op) {
	case '+':
        case '-':
	   p = 1;
	   break;
	case '*':
	case '/':
	   p = 2;
	   break; 
	default:
	   p = 0;
	   break;
    }
    return p;
}

string prefix(char *infix)
{
    stack<char> myStack;
    string rtn;
    int i = 0;
    while (1) {
	switch(infix[i]) {
	    case '\0':
		while(!myStack.empty()) {
	            rtn.push_back(myStack.top());
		    myStack.pop();	
		}
		return rtn;
	    case '(':
		myStack.push('(');
		break;
	    case '+':
	    case '-':
	    case '*':
	    case '/':
		while(!myStack.empty() && (getPriority(myStack.top()) >= getPriority(infix[i]))) {
		    rtn.push_back(myStack.top());
		    myStack.pop();
		}
		myStack.push(infix[i]);
		break;
	    case ')':
		while (!myStack.empty() && myStack.top() != '(') {
		    rtn.push_back(myStack.top());
		    myStack.pop();
		}
		myStack.pop();
		break;
	    default:
		rtn.push_back(infix[i]);
		break;
	}
	i++;
    }
    return rtn;
}

double cal(double a, double b, char op)
{
    switch(op) {
	case '+':
	    return a+b;
	case '-':
	    return a-b;
	case '/':
	    return a/b;
	case '*':
	    return a*b;
    }
}

int posfixEval(const char *posfix)
{
    double val = 0;
    stack<double> myStack;
    int i = 0;

    while(1) {
	switch(posfix[i]) {
	    case '+':
	    case '-':
	    case '*':
	    case '/':
	    
		if (!myStack.empty()) {
		    double num1 = myStack.top();
		    myStack.pop();
		    double num2 = myStack.top();
		    myStack.pop();
		    val = cal(num2, num1, posfix[i]);
		    myStack.push(val);
		}
		break;
	    case '\0':
		return val;
	    default:
		myStack.push(posfix[i]-'0');
		break;
	}
	i++;
    }
}

int main(int argc, char **argv)
{
    string posfix = prefix("1+2*(3+4)/2"); 
    cout << posfix << endl;
    int value = posfixEval(posfix.c_str());
    cout << value << endl;
}
